МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
Державний університет “Львівська політехніка”
АЛГОРИТМ РІШЕННЯ ЗАДАЧІ КОМІВОЯЖЕРА
І Н С Т Р У К Ц І Я
до лабораторної роботи № 3
з курсу
“Дискретні моделі в САПР”
для базового напрямку 6.0804 “Комп’ютерні науки”
Затверджено:
на засіданні кафедри “Системи
автоматизованого провектування”
Протокол N 14 від 03.04.1997 р.
Львів - 1998
Алгоритм рішення задачі комівояжера. Інструкція до лабораторної роботи N3 з курсу “Дискретні моделі в САПР” для базового напрямку 6.0804 “Комп’ютерні науки”
/Склали: В.І.Каркульовський, С.П.Ткаченко, І.І.Чура. -Львів: ДУ “Львівська політехніка”, 1998.
Укладачі: В.І.Каркульовський, канд.техн.наук, доц.,
С.П.Ткаченко, канд.техн.наук, доц.
І.І.Чура, канд.техн.наук, доц..
Відповідальний за випуск: Д.В.Федасюк, канд.техн.наук, доц.
Рецензенти: Стех Ю.В. , канд.техн.наук, доц.
Мотика І.І. , канд.техн.наук, доц.
1. МЕТА РОБОТИ
Метою даної лабораторної роботи є вивчення і дослідження алгоритмів рішення задачі комівояжера.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
ФОРМУЛЮВАННЯ ТА ДЕЯКІ ВЛАСТИВОСТІ ЗАДАЧІ КОМІВОЯЖЕРА
Комівояжеру потрібно відвідати кожне місто в певній зоні обслуговування і повернутися додому. Відомо, що комівояжеру хотілось би вибрати такий порядок обходу клієнтів, при якому його шлях був би найкоротшим. Таким чином, комівояжер зтикається із задачою пошуку маршрута мінімальної довжини, тривалості чи вартості.
Задача комівояжера може бути сформульована, як задача на графі. Для цього необхідно побубувати граф G=(X,A), вершини якого відповідають містам в зоні комівояжера, а ребра(дуги) відображають комунікації, що з’єднують пари міст. Довжина a=(x,y)0 кожної дуги (x,y)A може бути рівна відстані, вартості чи часу або числовому значенню деякого комплексного критерію.
Контур, що включає кожну вершину графа G хоча б один раз, називають маршрутом комівояжера. Контур, який включає кожну вершину графа G рівно один раз називають гамільтоновим.
Загальною задачею комівояжера називають задачу пошуку маршруту найменшої довжини.
Задачею комівояжера називають задачу пошуку гамільторового контура найменшої довжини.
Контур комівояжера, який має найменшу довжину, називають оптимальним гамільтоновим контуром він є оптимальним рішенням задачі комівояжера. Оптимальний маршрут комівояжера не обов`язково є гамільтоновим контуром.
Виникає питання, в яких випадках гамільтоновий контур є рішенням загальної задачі комівояжера? Відповідь дає наступна теорема.
Теорема 1. Якщо для кожної пари вершин (х,у) виконується умова:
a(x,y)a(x,z)+a(z,y) , для всіх zxy. (1)
то гамільтоновий контур є рішенням загальної задачі комівояжера на графі G (якщо рішення задачі взагалі існує).
Умова (1) говорить лише про те, що відстань безпосередньо від х до у ніколи не перевищує відстані від х до у через будь-яку іншу вершину z. Умову (1) називають нерівностю трикутника.
УМОВИ ІСНУВАННЯ ГАМІЛЬТОНОВОГО КОНТУРУ.
НИЖНІ ГРАНИЦІ.
Рішенням задачі комівояжера є оптимальний гамільтоновий контур. Нажаль, не всі графи містять гамільтоновий контур. Отже перед тим, ніж перейти до пошуку оптимального гамільтонового контура потрібно довести факт його існування в даному графі.
Введемо ряд визначень, які в подальшому нам знадобляться. Граф називається сильно зв`язаним, якщо в ньому для будь-яких двох вершин “х” і “у” існує шлях від “х” до “у”. Підмножина вершин Х деякого графа називається сильно зв`язаною, якщо для будь-яких пар вершин х Х і у Х існує шлях з “х” в “у” і Х не є підмножиною ніякої іншої множини вершин, які володіють тими ж властивостями. Сформулюємо загальну теорему Гуйя-Урі.
Теорема 2. Якщо граф G(X,A) задовільняє умовам :
1) граф G силно зв’язаний ;
2) d(х)n для всіх х ( Х, де d(x) - степінь вершини х, п - кількість вершин, то він містить гамільтоновий контур.
На практиці достатньо легко встановити, чи задовільняє деякий граф умовам (I.) і (II.) теореми 2.
Умова (1.) перевіряється застосуванням до кожної пари вершин алгоритма Флойда або алгоритма Данцига для поб...
